package 剑指offer;

import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2021-12-10 9:39
 */
public class day30_17_51 {

    /**==============================================================================================================================================
     * 剑指 Offer 17. 打印从1到最大的n位数
     * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
     *  */
    public int[] printNumbers(int n) {
        int maxnum=10;
        for (int i = 1; i < n; i++) {
            maxnum*=10;
        }
        maxnum=maxnum-1;
        int[] res=new int[maxnum];
        for (int i = 0; i < res.length; i++) {
            res[i]=i+1;
        }
        return res;
    }
    /**==============================================================================================================================================
     * 剑指 Offer 17. 打印从1到最大的n位数
     * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
     * 考虑大数打印时，需要用字符串存储，观察可知，生成的列表实际上是 n 位 0 - 9 的 全排列
     * 需要考虑删除高位多余的0： 声明变量 start 规定字符串的左边界，以保证添加的数字字符串 num[start:] 中无高位多余的 0
     *  观察可知，当输出数字的所有位都是 9 时，则下个数字需要向更高位进 1 ，此时左边界 start 需要减 1 （即高位多余的 0 减少一个）：所有位都为 99 的判断条件可用以下公式表示：n−start=nine
     *  */
    //回溯：路径：前面已经选择好的字符串序列
    //选择列表：0-9个字符
    //终止条件：path中的元素个数已经为n个，即已经成为了n位数
    LinkedList<String> res=new LinkedList<>();
    int nine=0,count=0,start,n;
    char[] loop={'0','1','2','3','4','5','6','7','8','9'};
    void backtrack(int index,String path){
        if (index==n){
            //已经为n位数了，需要去除前面多余的0
            String s=path.substring(start);
            if (!s.equals("0")) res.addLast(s);
            if (n-start==nine) start--;return;
        }
        for (char i:loop) {
            //做出选择
            if (i=='9') nine++;
            backtrack(index+1,path+String.valueOf(i));
        }
        nine--;
    }
    public LinkedList<String> printNumbers1(int n) {
        this.n=n;
        this.start=n-1;
        backtrack(0,"");
//        res.pollFirst();
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 51. 数组中的逆序对
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     * 归并排序思想：在归并排序的合并阶段统计「逆序对」数量，完成归并排序时，也随之完成所有逆序对的统计。
     *  */
    int[] nums,temp;
    int mergeSort(int l,int r){
        //终止条件
        if (l>=r) return 0;
        int m=(l+r)/2;
        int res=mergeSort(l,m)+mergeSort(m+1,r);
        //合并：
        int i=l,j=m+1;
        //需要一个辅助数组将[l，r]之间的复制出来，这样就在nums原数组上进行merge
        for (int k = l; k <= r; k++) {
            temp[k]=nums[k];
        }
        for (int k = l; k <=r ; k++) {
            if (i==m+1){
                nums[k]=temp[j++];
            }else if (j==r+1||temp[i]<=temp[j]){
                nums[k]=temp[i++];
            }else {
                nums[k]=temp[j++];
                res+=(m-i+1);//统计逆序对
            }
        }
        return res;
    }
    public int reversePairs(int[] nums) {
        int n=nums.length;
        if (n<2) return 0;
        this.nums=nums;
        temp=new int[nums.length];
        return mergeSort(0,nums.length-1);
    }

    public static void main(String[] args) {
        day30_17_51 obj=new day30_17_51();
        System.out.println(obj.printNumbers1(1));
    }
}
